package algorithm_demo.demo01;

/**
 *
 * 单链表和双链表的定义
 * 单链表：值，一条next指针
 * 双链表：值，一条last指针，一条next指针
 * @author Api
 * @date 2023/1/27 16:21
 */
public class Code15_LinkedList {

    //单链表
    public static class Node{
        private int value;
        private Node next;
        public Node(int value){
            this.value = value;
        }
    }

    //双链表
    public static class DoubleNode{
        private int value;
        private DoubleNode last;
        private DoubleNode next;

        public DoubleNode(int value){
            this.value = value;
        }
    }

    //单链表反转Code
    public static Node reverseLinkedList(Node head){
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;//记录原head的下一个指针是谁
            head.next = pre;//首次为null，第二次则被赋值上一次的Node（即head）
            pre = head;//pre跳到当前的Node
            head = next;//一直向右移动指针
        }
        return pre;
    }

    //双链表反转Code
    public static DoubleNode reverseDoubleLinkedList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
}
